1. Technical Field
The present invention relates in general to a system and method for scheduling processes requiring service, e.g., processes arising in multitasking operating systems or data communication links. More particularly, the present invention relates to a system and method for determining whether to preempt a current job, e.g., thread, in favor of a newly ready job with a better priority.
2. Description of the Related Art
The operating system is arguably the most important program that runs on a computer. Every general-purpose computer has an operating system in order to run other programs. Operating systems perform basic tasks, such as recognizing input from the keyboard, sending output to the display screen, keeping track of files and directories, and controlling peripheral devices such as disk drives and printers.
For large systems, such as a UNIX™ based operating system, the operating system has even greater responsibilities and powers. It makes sure that different programs and users running at the same time do not interfere with each other.
Operating systems provide a software platform on top of which other programs, called application programs, can run. The application programs are usually written to run on top of a particular operating system. The choice of which operating system to use, therefore, determines to a great extent the applications that can run.
The operating system often includes a “kernel.” As the name implies, the kernel is at the core of the operating system and is loaded each time the system is started, also referred to as a system “boot.” The kernel manages the resources of the system, presenting them to the users as a coherent system. The user does not have to understand much, if anything, about the kernel in order to use the computer system. The kernel provides various necessary functions in the operating environment. The kernel manages the system's memory and allocates it to each process. It takes time for the kernel to save and restore the program's state and switch from one program to the next (called dispatching). This action needs to execute quickly because time spent switching between programs takes away from the time available to actually run the users' programs. The time spent in the “system state” where the kernel performs tasks like switching between user programs is the system overhead and should be kept as low as possible.
The kernel also schedules the work to be done by the central processing unit, (also called “CPU” or “processor”) so that the work of each user is carried out efficiently. The kernel transfers data from one part of the system to another. Switching between user programs in main memory is also done by the kernel. One challenge facing traditional systems is efficiently running user programs so that the system overhead is minimized and more CPU time is spent running user programs.
Programs include one or more processes that are individually executed by the processor. As used herein, the terms “task,” “process,” “thread,” “job,” “program,” and “work” are used interchangeably to describe sets of instructions that are performed by the processor. Processes have priorities that determine their relative accessibility to a processor. One component of the kernel is the scheduler. As its name implies, the scheduler determines, based on priority, the order in which jobs are serviced by the processor (or processors in a multiprocessor system). A single processor can perform only one computer instruction at a time. But, because it can be interrupted, the processor can take turns in which programs or sets of instructions that it performs. An operating system usually has some code that is called an interrupt handler. The interrupt handler makes waiting work ready to run as the events delaying that work occur. This newly ready work is then stored in one or more queues where ready work waits until it is its turn to run based on its priority.
Preemptive multitasking is used to determine how long to allocate to any one process before giving another process a turn to use the operating system. The act of taking control of the operating system from one task and giving it to another task is called “context switching” which is triggered when one process “preempts” another process according to a priority algorithm used by the operating system. In addition, context switching occurs when a process uses its allotted processor time and is “time sliced” so that other processes can receive service from the processor. In some operating systems, some applications can be given higher priority than other applications, giving the higher priority programs preferential treatment by the scheduler as compared with lower priority programs. Time slicing and the priority algorithm in place in the operating system determine how much processor time any thread receives, subject to preemption by better priority threads.
In traditional systems that preempt based upon priority, a job with more favored priority preempts a job that is currently being serviced with a less favorable priority. One challenge caused by preempting jobs is the overhead needed by the system to interrupt the work currently being performed, queue the work to a queue managed by the scheduler, and start processing the job with the more favored priority. This increased overhead, in turn, can affect the overall performance and throughput of the computer system.
What is needed, therefore, is a system and method for providing a “less strict” preemption policy whereby a currently running job is not preempted when the newly ready work has a slightly higher priority, yet still allows newly ready work with a substantially higher priority to preempt the currently running job.